﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Geometry.ConvexHull
{
    public class ConvexHullStateSpace : IForwardStateSpace<ConvexHullStateSpace.State,IEnumerable<LinkedListNode<Point2D>>>
    {
        private readonly IEnumerable<Point2D> _points;

        public ConvexHullStateSpace(IEnumerable<Point2D> points)
        {
            var pointsSeq = points.ToList();
            if ( pointsSeq.Count < 3)
            {
                throw new ArgumentException("points must contains at least three or more points", "points");
            }
            var minY = pointsSeq.ArgMin(pt => pt.Y);
            var p = pointsSeq.Where(pt => pt.Equals(minY)).ArgMax(pt => pt.X);
            pointsSeq.Remove(p);
            pointsSeq.Sort((pt1, pt2) =>
                               {
                                   var atanPt1 = Math.Atan2(p.Y - pt1.Y, p.X - pt1.X);
                                   var atanPt2 = Math.Atan2(p.Y - pt2.Y, p.X - pt2.X);
                                   if (atanPt1 == atanPt2)
                                   {
                                       return pt1.X.CompareTo(pt2.X);
                                   }
                                   return atanPt1.CompareTo(atanPt2);
                               });
            _points = new[] { p}.Concat(pointsSeq);

        }

        public class State
        {
            private readonly LinkedList<Point2D> _points;
            private LinkedListNode<Point2D> _front;

            public LinkedList<Point2D> Points
            {
                get { return _points; }
            }

            public LinkedListNode<Point2D> Front
            {
                get { return _front;  }
                set { _front = value; }
            }

            public State(IEnumerable<Point2D> sortedPoints)
            {
                _points = new LinkedList<Point2D>(sortedPoints);
                _front = _points.First.Next.Next.Next;
            }
        }

        #region Implementation of IForwardStateSpace<State,IEnumerable<LinkedListNode<Point2D>>>

        public State Decide(State state, IEnumerable<LinkedListNode<Point2D>> decision)
        {
            state.Front = state.Front.Next;
            foreach(var discarded in decision)
            {
                state.Points.Remove(discarded);
            }
            return state;
        }

        public IEnumerable<IEnumerable<LinkedListNode<Point2D>>> Decisions(State state)
        {
            var node = state.Front.Previous;
            var discarded = new List<LinkedListNode<Point2D>>();
            while ( Utils.Right(node.Previous.Value,node.Value,state.Front.Value))
            {
                discarded.Add(node);
                node = node.Previous;
            }
            yield return discarded;

        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(_points); }
        }

        public bool IsFinal(State state)
        {
            return state.Front == null;
        }

        #endregion
    }

    public class ConvexHullSolver
    {
        private readonly GreedySolver<ConvexHullStateSpace.State, IEnumerable<LinkedListNode<Point2D>>, IEnumerable<Point2D>> _solver;

        public ConvexHullSolver()
        {
            _solver = new GreedySolver
                <ConvexHullStateSpace.State, IEnumerable<LinkedListNode<Point2D>>, IEnumerable<Point2D>>
                (
                createSolution: (space, d, f) => f.Points);
        }

        public IEnumerable<Point2D> Solve(IEnumerable<Point2D> points)
        {
            var stateSpace = new ConvexHullStateSpace(points);
            return _solver.Solve(stateSpace);
        }
    }
}
